1. Field of the Invention
The present invention relates to a method for searchable symmetric encryption, and more particularly, to a method for searchable symmetric encryption capable of providing efficient range search by using a linked graph.
2. Description of the Related Art
A modern society is changed into a society that digitalizes and stores all information and shares and uses the stored information through a network. Further, due to the increase in the amount of processed data and demands for various services, various specialized external storage space are being extensively utilized.
Moreover, security of information stored in the external storage space has become an issue. Security in the external storage space is different from when individuals managed information by oneself using an independent storage space. The reason for this is that an information owner is fundamentally different from one that manages the external storage space. An access control technique or a key management technique which is principally used to protect the information in a database is effective in preventing an external intruder, but the techniques cannot fundamentally prevent a manager of the external storage space from reading data stored in the corresponding storage means.
As a result, data encryption may be used as a method for safely storing the information. That is, information to be stored in the external storage space is encrypted by using an encryption system proven to be secure. The encryption system having the proved safety ensures that an attacker who does not own a decryption key cannot acquire stored information from ciphertext. Therefore, even though the external intruder or the manager of the storing space access the stored ciphertext, they do not actually obtain any significant information. Meanwhile, encryption of information is a method for perfectly securing confidentially stored information, but the information encryption also disables many additional functions provided from the general database. That is, as the amount of stored information increase, various database functions are required to efficiently utilize and manage the stored information. Therefore, a method for simply encrypting and storing the information is not applicable.
A searchable encryption protocol is contrived to search for data including a predetermined keyword while ensuring the confidentiality of the encrypted information like the general encryption system. Since most of the various functions provided from the database are based on keyword search, the searchable encryption system is considered as one of the solutions to the above-mentioned problems.
In the searchable encryption system, it is assumed that each document consists of several keywords, and the query is determined by keywords that the user wants to search. Because ciphertext in encryption systems reveals no information about an encrypted data, searchable encryption provides a clue for searching, which is called an ‘index’. An index contains information about the relations between keywords and encrypted data. However, an index is also locked in order to keep it secret, and can only be opened by those possessing a special key, called a ‘trapdoor’. Since a search is executed by the database server, to conduct one, the user has to generate and hand over a trapdoor to the server.
Usually, searchable encryption consists of four algorithms: key generation, build index, trapdoor generation, and search. In the key generation step, the user chooses an encryption system and prepares other parameters including encryption and decryption keys. A set of data and system parameters are given to the build index algorithm as an input. The build index algorithm outputs encrypted data and indexes. Outputs of the build index algorithm are sent to the server and stored. If the user wants to search for data, then the user runs the trapdoor generation algorithm. The keywords that the user wants to use in the search and the user's secret key are input into the trapdoor generation algorithm. After the trapdoor is given to the server, the server runs the search algorithm. The trapdoor and indexes are input for the search, and the result of the search algorithm is a set of documents corresponding to the queried keyword. Finally, the result of the search is given to the user.
Basic searchable encryption provides a search algorithm that finds documents corresponding to just one specific keyword. However, this search algorithm is very limited and cannot satisfy various demands that naturally arise. Therefore, designing a searchable encryption with useful additional functions is an important goal in searchable encryption. Frequently mentioned additional functions are conjunctive keyword search, range search, ordering, size comparison, and arbitrary search etc. The present patent concentrates on the range search.
Formally, a range search is a search of documents of which corresponding keywords are included within a set of successive keywords, an interval, rather than as a single keyword. To achieve a range search regarding an interval [a, b] using ordinal searchable encryption, the user has to do simple keyword searches b−a+1 times repeatedly. This is a very inefficient and insecure method. Because the server, which actually runs the search algorithm, trivially obtains information regarding the size of the range and can also divide the result into b−a+1 subsets, each subset actually corresponds to a single keyword.
The research results for the range search are very infrequent until now. U.S.A. patent laid open publication No. 2005-014724 (System and Method for Fast Querying of Encrypted Databases) discloses a searchable encryption system supporting the range search for the encrypted data. This method uses a scheme that divides data into segments having any size and encrypts them into a segment unit (data included in the same segment is encrypted by the same encryption key). The method further requires a post-processing process to remove a false hit included in the searching result and has lower safety than the encryption method.
“‘Conjunctive, Subset and Range Queries on Encrypted Data,’ TCC 2007, LNCS 4392, pp 535-554, 2007” by Boneh, et al., discloses a safety model for a coupling keyword search, a subset search, and a range search and a searchable encryption system supporting various types of searches having safety verified by the model. The method provides verifiable safety by a public key based design but requires a lot of time to perform bilinear and public key operation.
“‘Searchable Symmetric Encryption Improved Definitions and Efficient Constructions,’ Proc of the ACMCCS, Proc. of the 13th ACMCCS 2006, pp. 79-88, 2006” by Curtmola et al., discloses a searchable encryption system based on a linked chain. The method is very efficient in terms of a searching speed but does not disclose a further function of a range search, and the like.